1. Field of the Invention
The present invention relates to object-based computing systems. More specifically, the present invention relates to a method and an apparatus that facilitates bulk lock-unbiasing for objects within an object-based computing system.
2. Related Art
Object-based computer programs differ from typical function-based computer programs because each element of computation in an object-based computer program is associated with an “object.” Furthermore, the structure of each object is defined by an associated data type called a “class.”
Many object-based computer systems support “multi-threading.” In such multi-threaded systems, multiple threads of execution may attempt to access the same object simultaneously, which can lead to contention problems. For example, FIG. 1 illustrates how a thread 102 and a thread 104 attempt to execute the same method 108 within object instance 106.
To correctly arbitrate between these concurrent executions, the object is typically associated with a mutual-exclusion primitive, such as a mutex or monitor. There is a large body of literature describing various techniques and paradigms for implementing these mutual-exclusion primitives.
Processors that support multi-threading typically provide “atomic operations,” which can be used to implement mutual-exclusion primitives. These atomic operations are guaranteed to execute without interference from concurrently executing threads, and without interference from threads on other processors. Because of the complexity involved in ensuring that atomic operations execute without interference from other threads, atomic operations are considerably more time-consuming to execute than ordinary operations, such as additions and subtractions.
A thread can use mutual-exclusion primitives to “lock” specific objects to reduce interference, but this uses numerous atomic operations. To reduce locking overhead, a system can allow objects to be “biased” towards specific threads, thereby allowing threads to access biased objects as if they were locked, but without atomic operations. However, this capability can lead to situations in which a large number of biased objects need to be unbiased, in which case the system often has to search the entire object heap to find and unbias the desired objects. This bulk-unbiasing operation can be very computationally expensive, and does not scale well for processes with large object heaps.
Hence, what is needed is a method and an apparatus for facilitating bulk lock-unbiasing without the limitations of the above-described techniques.